/*
 * @lc app=leetcode.cn id=128 lang=javascript
 *
 * [128] 最长连续序列
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
class unionSet {
  constructor () {
    this.father = {};
    this.size = {};

    this.max = 1;
  }
  find(x) {
    if (this.father[x] === undefined) this.father[x] = x;
    return this.father[x] = this.father[x] === x ? x : this.find(this.father[x]);
  }
  merge(a, b) {
    let fa = this.find(a), fb = this.find(b);
    if (fa === fb) return;
    this.father[fa] = fb;

    if (this.size[fa] === undefined) this.size[fa] = 1;
    if (this.size[fb] === undefined) this.size[fb] = 1;
    this.size[fb] += this.size[fa];

    this.max = Math.max(this.max, this.size[fb]);
  }
}

var longestConsecutive = function (nums) {
  if (!nums.length) return 0;

  const u = new unionSet(nums.length);

  for (let i = 0; i < nums.length; i++) {
    const num = nums[i];
    if (nums.includes(num - 1)) u.merge(num, num - 1);
  }

  return u.max;

  // let max = 1;
  // for (let i = 0; i < nums.length; i++) {
  //   const num = nums[i];
  //   const fNum = u.find(num);
  //   if(u.size[fNum] > max) max = u.size[fNum];
  // }
  // return max;
};
// @lc code=end

